package com.clstu.sort;

import java.util.Arrays;

/**
 * 研究希尔排序(插入排序的升级版(分组插入法,每次分组主键减小,直到只有一组)!!)
 */
public class ShellSort {
    public static void main(String[] args) {
        //测试希尔排序,
//        int[] arr = {8,9,1,7,2,3,5,4,6,0};
//        shellSort(arr);

        //测试速度
        int[] arr = new int[8000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i]= (int) (Math.random()*80000);
        }
//        System.out.println("排序前:"+Arrays.toString(arr));
        long start = System.currentTimeMillis();
        shellSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("希尔排序"+arr.length+"个数据耗时:"+(end-start)+"ms");//17ms,跟冒泡,插入,选择法排序不是一个量级的(远高于)
//        System.out.println("排序后:"+Arrays.toString(arr));

        start = System.currentTimeMillis();
        shellSort(arr);
        end = System.currentTimeMillis();
        System.out.println("希尔排序"+arr.length+"个数据(有序的)耗时:"+(end-start)+"ms");//2ms
    }

    //编写方法实现希尔排序
    public static void shellSort(int[] arr){
        //思路:因为插入排到排序最后可能会导致一个很小的数要移位很多次才能到最后的位置
        //于是希尔排序解决了这个问题,先分成很多组,每组间隔跨度很大,每一组分别插入排序,
        // 这样就能一下将很小很远的元素一下拉到与正确位置靠近的位置
        //希尔排序过程:
        //分组,组数的规律是gap(组数)=arr.length/2/2/2/2/....直到为1为止(i组的元素i,i+gap,i+gap+gap,...)
        //对每一组都用插入排序,直到最后只剩下一组
        //最后一组排完序后就已经有序了
        int insertVal;
        int insertIndex;
        int count = 0;
        for (int gap = arr.length/2;gap>=1;gap = gap/2){
            //里面的两层循环是插入排序(分组版本的,其实每组都是现了插入排序,因为是i++而不是i+=gap,所以每一组都会执行插入排序)
            for (int i = gap; i < arr.length; i++) {
                insertVal = arr[i];
                insertIndex = i-gap;
                while (insertIndex >= 0 && insertVal < arr[insertIndex]){
                    arr[insertIndex+gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                //循环结束,就是可以插入的位置
                if(insertIndex+gap != i) {
                    arr[insertIndex + gap] = insertVal;
                }
            }
            //查看结果
//            System.out.println("希尔排序第"+(++count)+"分组后排序的结果:"+ Arrays.toString(arr));
        }

    }
}
